// 给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。

// 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。

// 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/island-perimeter
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<bits/stdc++.h>
using namespace std;

class Solution
{
private:
    /* data */
public:
    int islandPerimeter(vector<vector<int>>& grid){
        int x=-1,y=-1;
        for(int i=0;i<grid.size();++i){
            for(int j=0;j<grid[0].size();++j){
                if(grid[i][j]==1){
                    x=i,y=j;
                    break;
                }
            }
            if(x!=-1){
                break;
            }
        }
        if(x==-1){
            return 0;
        }

        int res =0;
        queue<pair<int,int>> que;
        que.emplace(x,y);
        grid[x][y]=2;
        int dire[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
        while(!que.empty()){
            auto [xx,yy]=que.front();
            que.pop();
            for(int i=0;i<4;++i){
                int nx=xx+dire[i][0];
                int ny=yy+dire[i][1];
                if(nx<0 ||nx>=grid.size() || ny<0 || ny>=grid[0].size() || grid[nx][ny]!=1){
                    if(nx<0 ||nx>=grid.size() || ny<0 || ny>=grid[0].size() || grid[nx][ny]==0){
                        ++res;
                    }
                    continue;
                }
                if(grid[nx][ny]==1){
                    que.emplace(nx,ny);
                    grid[nx][ny]=2;
                }
            }
        }
        return res;
    }
};



int main(int argc, char const *argv[])
{
    vector<vector<int>> grid={{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}};
    Solution s;
    int res = s.islandPerimeter(grid);
    cout<<res<<endl;
    return 0;
}
